package problems;

import java.util.HashSet;
import java.util.Set;

import lib.MathLib;


public class Euler346 extends AbstractEuler {

	@Override
	public Number calculate() {
		//i in base i - 1 is always written "11", so to be a strong repunit, it only needs to be representable as "11(1)+" once more.
		//The largest candidate strong repunit below 10^12 would be 999999999999, considering that it is "11" in base 999999999998.
		//the greatest base bMax for which "111" would represent a number smaller than 10^12 would be just below sqrt(10^12) = 10^6.
		//alternatively: the base satisfying bMax^2 + bMax + 1 < 10^12 (solve with quadratic formula). 111 in base 999999 equals 999999000001.
		//any smaller numbers represented as "11(1)+" in any base would be of a smaller base, so all we have to do is calculate what
		//all numbers "11(1)+" in any base below 1000000 are, weed out duplicates by using a Set, and sum them.
 
		Set<Long> strongRepunits = new HashSet<Long>();
		
		for (int base = 2; base <= 999999; base++) {
			for (long length = 3, allOnesInBase = allOnesInBase(base, (int)length); allOnesInBase < 1000000000000L; allOnesInBase = allOnesInBase(base, (int)++length)) {
				strongRepunits.add(allOnesInBase);
			}
		}
		System.out.println();
		return MathLib.getSum(strongRepunits) + 1; //1 is a repunit in all bases
	}
	
	private long allOnesInBase(int base, int length) {
		long result = 1, factor = 1;
		for (int i = 1; i < length; i++) {
			factor *= base;
			result += factor;
		}
		return result;
	}
	
	@Override
	protected Number getCorrectAnswer() {
		return 336108797689259276L;
	}

}
